package com.lry.basic.algorithm.common;

import java.util.ArrayList;
import java.util.List;

/**
 * 字符串筛选排序 | 时间限制：1秒 | 内存限制：32768K | 语言限制：不限
 * 输入一个由n个大小写字母组成的字符串，按照Ascii码值从小到大的排序规则，
 * 查找字符串中第k个最小ascii码值的字母（k>=1），输出该字母所在字符串的位置索引(字符串的第一个字符位置索引为0）。
 * k如果大于字符串长度，则输出最大ascii值的字母所在字符串的位置索引，如果有重复的字母，则输出字母的最小位置索引。
 *
 * 输入描述:
 * 第一行输入一个由大小写字母组成的字符串
 * 第二行输入k，k必须大于0，k可以大于输入字符串的长度
 * 输出描述:
 * 输出字符串中第k个最小ascii码值的字母所在字符串的位置索引。k如果大于字符串长度，则输出最大ascii值的字母所在字符串的位置索引，如果第k个最小ascii码值的字母存在重复，则输出该字母的最小位置索引。
 *
 * 示例1
 * 输入
 * AbCdeFG
 * 3
 * 输出
 * 5
 *
 * 示例2
 * 输入
 * fAdDAkBbBq
 * 4
 * 输出
 * 6
 */
public class TopKChar {

    public static void main(String[] args) {
        System.out.println(new TopKChar().topKCharIndex("fAdDAkBbBqq", 111));
    }

    private int topKCharIndex(String str,int k){
        if(k>str.length()){
            k = str.length();
        }
        CharHelper[] helper = new CharHelper[123];

        for(int i=0;i<str.length();i++){
            char c = str.charAt(i);
            CharHelper charHelper = helper[c];
            if(null==charHelper){
                charHelper = new CharHelper();
            }
            charHelper.incrCount();
            charHelper.setMinIndex(i);

            helper[c] = charHelper;
        }


        for(int i=65; i<=122; i++){
            CharHelper charHelper = helper[i];
            if(null==charHelper){
                continue;
            }

            k -= charHelper.count;
            if(k<=0){
                return charHelper.minIndex;
            }
        }

        return -1;
    }

    class CharHelper{
        public int count;
        public int minIndex = -1;

        public void incrCount(){
            count++;
        }

        public void setMinIndex(int index){
            if(-1==minIndex){
                minIndex = index;
            }else{
                if(index<minIndex){
                    minIndex = index;
                }
            }
        }
    }

}
